package main.技巧;

import java.util.Arrays;

/**
 * @author tmh
 * @date 2024/9/22 16:25
 * @description
 */
public class T31下一个排列 {
    public void nextPermutation(int[] nums) {
        //从右往做找到第一个升序的，然后再翻转后面的数字
        int len = nums.length;
        int index = len - 1;
        boolean flag = true;
        while (index > 0) {
            if (nums[index - 1] < nums[index]) {
                flag = false;
                break;
            } else {
                index--;
            }
        }
        if (flag) {
            reverse(nums, 0);
        } else {
            //找到第一个升序的数字
            index = index - 1;
            //然后再去找第一个大于这个数字的数,然后再交换
            for (int j = len - 1; j >= 0; j--) {
                if (nums[j] > nums[index]) {
                    int temp = nums[j];
                    nums[j] = nums[index];
                    nums[index] = temp;
                    //只需要找第一个就好了，所以这里需要break下
                    break;
                }
            }
            //然后再去翻转index+1后面的数字
            reverse(nums, index + 1);
        }
    }

    private void reverse(int[] nums, int start) {
        int end = nums.length - 1;
        while (start < end) {
            int temp = nums[start];
            nums[start] = nums[end];
            nums[end] = temp;
            start++;
            end--;
        }
    }
}
